import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author VernHe
 * @date 2021年07月04日 22:29
 */
public class Solution_0301 {
    /**
     * 字符串长度
     */
    private int len;
    /**
     * 字符串转换的数组
     */
    private char[] charArray;
    /**
     * 存放结果
     */
    private Set<String> result = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        // 初始化
        len = s.length();
        charArray = s.toCharArray();
        // 得到要删除的左括号和右括号的数量，遇到一对就会抵消
        int leftRemove = 0, rightRemove = 0;
        for (int i = 0; i < len; i++) {
            if (charArray[i] == '(') {
                leftRemove++;
            } else if (charArray[i] == ')') {
                if (leftRemove == 0) {
                    // 不能进行抵消
                    rightRemove++;
                } else {
                    // 抵消
                    leftRemove--;
                }
            }
        }
        // 用于记录路径
        StringBuilder path = new StringBuilder();
        // dfs进行回溯
        dfs(0,0,0,leftRemove,rightRemove, path);
        // 返回结果
        return new ArrayList<>(result);
    }

    private void dfs(int index, int leftCount, int rightCount, int leftRemove, int rightRemove, StringBuilder path) {
        // 递归基
        // 如果遍历完，就判断一下此时是否消掉了所有多余括号
        if (index == len) {
            if (leftRemove == 0 && rightRemove == 0) {
                result.add(path.toString());
            }
            // 回退
            return;
        }
        /**
         * 当前遍历到的字符
         */
        char curChar = charArray[index];

        // 如果可以删除，当前括号舍去（不加入path），继续dfs
        if (curChar == '(' && leftRemove > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemove - 1, rightRemove, path);
        }
        if (curChar == ')' && rightRemove > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove - 1, path);
        }

        // 不删除，路径上增加这个括号，继续dfs
        path.append(curChar);
        // 如果是字母就什么都不做
        // 如果是右括号，并且右括号的数量小于左括号的数量就继续递归（否则肯定是不合法的，进行回溯）
        if (curChar != '(' && curChar != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove, path);
        } else if (curChar == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemove, rightRemove, path);
        } else if (rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemove, rightRemove, path);
        }

        // 能到这里说明此次dfs执行完，发生了回溯！因此要把路径改回原样
        path.deleteCharAt(path.length() - 1);
    }
}
